package exercises.leetcode;

/**
 * <a href="https://leetcode-cn.com/problems/valid-sudoku/">
 * 36. 有效的数独</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 请你判断一个 9x9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
 * <p>
 * 数字 1-9 在每一行只能出现一次。
 * <p>
 * 数字 1-9 在每一列只能出现一次。
 * <p>
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
 * <p>
 * 数独部分空格内已填入了数字，空白格用 '.' 表示。
 * <p>
 * 注意：
 * <p>
 * 一个有效的数独（部分已被填充）不一定是可解的。
 * 只需要根据以上规则，验证已经填入的数字是否有效即可。
 *
 * @author or2
 * @date 2021年09月24日 时间: 8:47
 */
public class No36 {
    public boolean isValidSudoku(char[][] board) {
        /*使用位图暂存已有信息*/
//        short column = 0, row = 0, grid = 0; :因为对齐, 可能并不节省空间
        int[] bitmap = new int[9];
        /*填充位图, 检测错误*/
        for (int col = 0; col < board.length; col++) {
            for (int r = 0; r < board[0].length; r++) {
                char c = board[r][col];
                /*空的地方直接跳过*/
                if (c == '.') {
                    continue;
                }
                /*检测并填充*/
                short num = (short) (c - '1');
                /*行*/
                if ((bitmap[col] & 1 << num) > 0) {
                    return false;
                } else {
                    bitmap[col] |= 1 << num;
                }
                /*列*/
                int bitRow = 1 << num + 9;
                if ((bitmap[r] & bitRow) > 0) {
                    return false;
                } else {
                    bitmap[r] |= bitRow;
                }
                /*九宫格*/
                int bitGrid = 1 << num + 18;
                int grid = col / 3 * 3 + r / 3;
                if ((bitmap[grid] & bitGrid) > 0) {
                    return false;
                } else {
                    bitmap[grid] |= bitGrid;
                }
            }
        }

        return true;
    }
}
